(* Extract a given number of randomly selected elements from a list *)

(* 随机选择函数：从列表list中选取n个随机元素 *)
let rand_select list n =
  (* 固定随机种子为0，使结果可重现 *)
  Random.init 0;
  
  (* 辅助函数：从列表中提取第n个元素，返回该元素和剩余列表 *)
  let rec extract acc n = function
    | [] -> raise Not_found  (* 空列表时抛出异常 *)
    | h :: t -> 
        if n = 0 then (h, acc @ t)  (* 找到目标位置时返回元素和拼接后的剩余列表 *)
        else extract (h :: acc) (n - 1) t  (* 递归处理剩余元素 *)
  in
  
  (* 包装函数：从列表中随机提取一个元素 *)
  let extract_rand list len =
    extract [] (Random.int len) list  (* 生成随机索引并调用extract *)
  in
  
  (* 主递归函数：累积选择n个随机元素 *)
  let rec aux n acc list len =
    if n = 0 then acc  (* 已选够数量时返回结果 *)
    else
      let picked, rest = extract_rand list len in  (* 随机选取一个元素 *)
      aux (n - 1) (picked :: acc) rest (len - 1)  (* 递归处理剩余列表 *)
  in
  
  (* 计算原始列表长度，并调用主函数 *)
  let len = List.length list in
    aux (min n len) [] list len  (* 使用min防止请求数量超过列表长度 *)
;;


assert (rand_select [`a;`b;`c;`d;`e;`f;`g;`h] 3 = [`h;`a;`b]) ;; 
